This invention relates to programmable logic devices that are configured to accommodate multiplication. More particularly, this invention relates to programmable logic devices including logic elements having features that facilitate the performance of multiplication operations with minimal adverse impact on the performance of other operations of the logic elements.
Programmable logic devices ("PLDs") typically include (1) many regions of programmable logic, and (2) programmable interconnection resources for selectively conveying signals to, from, and/or between those logic regions. Each logic region is programmable to perform any of several different, relatively simple logic functions. The interconnection resources are programmable to allow the logic regions to work together to perform much more complex logic functions than can be performed by any individual logic region. Examples of known PLDs are shown in U.S. Pat. Nos. 3,473,160, Re. 34,363, 5,689,195 and 5,909,126, and U.S. patent application Ser. No. 09/266,235, all of which are hereby incorporated by reference herein in their entireties.
One of the functions that can be implemented in a PLD is the multiplication of one number by another. Typically, each the multiplicands in such an operation would have multiple bits. As is well known, the first step of such a multiplication can be performed by multiplying each bit of the first multiplicand by the least significant bit of the second multiplicand to form a first partial product. Next, the first multiplicand is shifted left one digit (in a binary number, that has the effect of multiplication by two) and multiplying each bit by the second least significant bit of the second multiplicand to form a second partial product. The same procedure is performed for the remaining bits of the second multiplicand (with appropriate additional shifting of the first multiplicand) to form additional partial products. All of the partial products are added together to form a sum, representing the desired product.
A multiplication operation such as that just described can be implemented in known PLDs, using the logic regions to perform the individual multiplications and summations, and using the interconnect network to route the intermediate results of those individual operations between the appropriate logic regions until the final result has been achieved. However, the need to route each intermediate result onto the general interconnect network results in a significant speed penalty in the determination of the final product. Moreover, the logic regions typically are optimized to perform the more common logic operations, rather than arithmetic operations. Therefore, the multiplication operation is slowed down within the logic regions as well. In addition, in some known devices in which provision for multiplication has been made, AND gates have been provided on the front end of each logic region to facilitate the formation of partial products and sums thereof, but all signals have to pass through those AND gates for all operations, slowing down non-multiplication operations.
It would be desirable to be able to provide a programmable logic device optimized to perform multiplication operations.
It would also be desirable to provide such a programmable logic device with little or no speed penalty in the performance of logic operations.